Network middleboxes are difficult to manage and troubleshoot due to their proprietary monolithic design. Moving towards Network Functions Virtualization (NFV), the virtualized appliances can be flexibly instantiated and dynamically chained, which makes troubleshooting middleboxes more difficult. To provide carrier-grade availability and reduce outages, operators attempt to verify that the automatically deployed network and middlebox configurations obey high-level network policies. Such network verification involves the modeling of middleboxes. A challenge while performing verification for network functions (NFs) and their service chains is the lack of middlebox models. NFs maintain states about each connection and perform different actions based on the states. The states also vary depending on the type of NF being verified. For example, a firewall tracks a Transmission Control Protocol (TCP) connection state, whereas a Deep Packet Inspection (DPI) tracks application payload. Currently, no abstraction to model disparate state for individual flows (or connections) for service function chaining (SFC) verification exists.